#include <bits/stdc++.h>
using namespace std;

/*
838. 推多米诺
已解答
中等
相关标签
相关企业
n 张多米诺骨牌排成一行，将每张多米诺骨牌垂直竖立。在开始时，同时把一些多米诺骨牌向左或向右推。

每过一秒，倒向左边的多米诺骨牌会推动其左侧相邻的多米诺骨牌。同样地，倒向右边的多米诺骨牌也会推动竖立在其右侧的相邻多米诺骨牌。

如果一张垂直竖立的多米诺骨牌的两侧同时有多米诺骨牌倒下时，由于受力平衡， 该骨牌仍然保持不变。

就这个问题而言，我们会认为一张正在倒下的多米诺骨牌不会对其它正在倒下或已经倒下的多米诺骨牌施加额外的力。

给你一个字符串 dominoes 表示这一行多米诺骨牌的初始状态，其中：

dominoes[i] = 'L'，表示第 i 张多米诺骨牌被推向左侧，
dominoes[i] = 'R'，表示第 i 张多米诺骨牌被推向右侧，
dominoes[i] = '.'，表示没有推动第 i 张多米诺骨牌。
返回表示最终状态的字符串。

 
示例 1：

输入：dominoes = "RR.L"
输出："RR.L"
解释：第一张多米诺骨牌没有给第二张施加额外的力。
示例 2：


输入：dominoes = ".L.R...LR..L.."
输出："LL.RR.LLRRLL.."
 

提示：

n == dominoes.length
1 <= n <= 105
dominoes[i] 为 'L'、'R' 或 '.'
*/

// 法一
class Solution {
	public:
	string pushDominoes(string dominoes) {
		int n = dominoes.size();
		vector<int> forces(n, 0);
		// 从左向右计算向右的力
		int force = 0;
		for (int i = 0; i < n; ++i) {
			if (dominoes[i] == 'R') {
				force = n;
			} else if (dominoes[i] == 'L') {
				force = 0;
			} else {
				force = max(force - 1, 0);
			}
			forces[i] += force;
		}
		// 从右向左计算向左的力
		force = 0;
		for (int i = n - 1; i >= 0; --i) {
			if (dominoes[i] == 'L') {
				force = n;
			} else if (dominoes[i] == 'R') {
				force = 0;
			} else {
				force = max(force - 1, 0);
			}
			forces[i] -= force;
		}
		// 根据合力决定最终状态
		string result;
		for (int f : forces) {
			if (f > 0) {
				result += 'R';
			} else if (f < 0) {
				result += 'L';
			} else {
				result += '.';
			}
		}
		return result;
	}
};

// 法二
class Solution {
	public:
	string pushDominoes(string dominoes) {
		int n = dominoes.size(), i = 0;
		char left = 'L'; // 初始左边界设为 'L'（虚拟边界）
		while (i < n) {
			int j = i;
			// 找到一段连续的竖立骨牌（'.'）
			while (j < n && dominoes[j] == '.') {
				j++;
			}
			// 右边界是下一个非竖立骨牌的方向，如果越界则设为 'R'（虚拟边界）
			char right = j < n ? dominoes[j] : 'R';
			// 情况1：左右边界方向相同
			if (left == right) {
				// 中间的竖立骨牌全部倒向该方向
				while (i < j) {
					dominoes[i++] = right;
				}
			}
			// 情况2：左边界是 'R'，右边界是 'L'
			else if (left == 'R' && right == 'L') {
				// 从两侧向中间依次推倒
				int k = j - 1;
				while (i < k) {
					dominoes[i++] = 'R';
					dominoes[k--] = 'L';
				}
			}
			// 其他情况（如左边界是 'L'，右边界是 'R'），中间的竖立骨牌保持竖立
			// 更新左边界为当前右边界，跳过已处理的非竖立骨牌
			left = right;
			i = j + 1;
		}
		return dominoes;
	}
};

// 法三
class Solution {
	public:
	string pushDominoes(string dominoes) {
		// 在原始字符串前后添加哨兵字符 'L' 和 'R'，简化边界条件处理
		// 这样就不需要单独处理字符串开头和结尾的特殊情况
		string s = "L" + dominoes + "R";
		int n = s.size();
		int pre = 0; // 记录前一个非 '.' 字符的位置，初始指向第一个哨兵 'L'

		for (int i = 1; i < n; i++) {
			if (s[i] == '.') {
				continue; // 跳过当前字符，继续处理下一个字符
			}

			// 情况1：当前字符和前一个非 '.' 字符相同（L...L 或 R...R）
			if (s[i] == s[pre]) {
				// 将这两个相同字符之间的所有 '.' 都变成当前字符
				fill(s.begin() + pre + 1, s.begin() + i, s[i]);
			}
			// 情况2：当前字符是 'L' 且前一个非 '.' 字符是 'R'（R...L）
			else if (s[i] == 'L') {
				// 计算中间位置，将区间分成两部分
				// 前一半（靠近 'R' 的部分）变成 'R'
				fill(s.begin() + pre + 1, s.begin() + (pre + i + 1) / 2, 'R');
				// 后一半（靠近 'L' 的部分）变成 'L'
				fill(s.begin() + (pre + i) / 2 + 1, s.begin() + i, 'L');
			}
			// 情况3：当前字符是 'R' 且前一个非 '.' 字符是 'L'（L...R）
			// 这种情况不需要处理，中间的 '.' 保持原状

			pre = i; // 更新前一个非 '.' 字符的位置
		}
		// 返回处理后的字符串，去掉前后添加的哨兵字符
		return s.substr(1, n - 2);
	}
};